package com.mamingchao.basic.heap;

import com.mamingchao.basic.arraysort.Sortable;

/**
 * Created by mlamp on 2024/5/13.
 *
 * 将 数组转换成 大根堆或者小根堆的堆结构
 * maxOrMinRootValue: 1-大根堆； 0-小根堆
 *
 * 数组遍历的index 值，从1开始，在计算子节点index或者父节点index，可以使用上 位运算
 * 所以此类一下的所有index，都是以 array 的初始index 从1开始 为基础
 */

public class HeapifyUtil implements Sortable {

    private static HeapifyUtil instance = new HeapifyUtil();

    public static HeapifyUtil getInstance(){
        return instance;
    }

    private HeapifyUtil(){}

    // 从下往上处理，时间复杂度 O(N)，比从上往下O(N*logN)小（是说当N非常非常大的时候）； 所以采用 从下往上的方式
    // public static <T> T heapify(T[] array, int maxOrMinRootValue){
    public void heapify(int[] array, int myIndex, int startIndex, int endIndex, int maxOrMinRootValue){

        if (maxOrMinRootValue == 1){
            maxRootValueHeapify(array, myIndex, endIndex);
        }

        if (maxOrMinRootValue == 0){
            minRootValueHeapify(array, startIndex, endIndex);
        }

    }

    private void minRootValueHeapify(int[] regularHeap, int myIndex, int endIndex){

        if (regularHeap == null || regularHeap.length == 0 )
            throw new RuntimeException("错误的初始heap数组");

        int minChildNodeIndex = this.getMinValueChildIndex(regularHeap, myIndex, endIndex);

        if (minChildNodeIndex == myIndex)
            return;

        while (minChildNodeIndex < endIndex) {
            if (regularHeap[myIndex-1] > regularHeap[minChildNodeIndex-1]){
                swap(regularHeap, myIndex-1, minChildNodeIndex-1);
                myIndex = minChildNodeIndex;
                 minChildNodeIndex = this.getMinValueChildIndex(regularHeap, myIndex, endIndex);
            }
            if (minChildNodeIndex == myIndex)
                break;
        }
    }

    private void maxRootValueHeapify(int[] regularHeap, int myIndex, int endIndex){

        if (regularHeap == null || regularHeap.length == 0 )
            throw new RuntimeException("错误的初始heap数组");

        int maxChildNodeIndex = this.getMaxValueChildIndex(regularHeap, myIndex, endIndex);

        if (maxChildNodeIndex == myIndex)
            return;

        while (maxChildNodeIndex < endIndex) {
            if (regularHeap[myIndex-1] < regularHeap[maxChildNodeIndex-1]) {
                swap(regularHeap, myIndex-1, maxChildNodeIndex-1);
                myIndex = maxChildNodeIndex;
                maxChildNodeIndex = this.getMaxValueChildIndex(regularHeap, myIndex, endIndex);
            }

            if (maxChildNodeIndex == myIndex)
                break;
        }
    }

    /**
     *
     * @param regularHeap 堆数组
     * @param nodeIndex 当前节点的 index
     * @param endIndex 子堆的索引做大值；即在nodeIndex ~ endIndex范围内 寻找当前node的 maxValueChild
     * @return 返回value更大的孩子的index；如果没有孩子节点，返回自己的index
     */

    private int getMaxValueChildIndex(int[] regularHeap,int nodeIndex, int endIndex) {

        // 左孩子的index
        int leftChildNodeIndex = this.getLeftChildNodeIndex(nodeIndex);
        // 右孩子的index
        int rightChildNodeIndex = leftChildNodeIndex + 1;

        int maxValueChildIndex = nodeIndex;

        // 如果有左孩子，即如果 当前node不是叶子节点，返回左节点的index
        if (leftChildNodeIndex < endIndex && regularHeap[leftChildNodeIndex-1] > regularHeap[nodeIndex-1])
            maxValueChildIndex = leftChildNodeIndex;

        // 如果 右孩子也存在，并且右孩子比左孩子的value还大，则返回右孩子的index
        if (rightChildNodeIndex < endIndex && regularHeap[rightChildNodeIndex-1] > regularHeap[leftChildNodeIndex-1] ){
            maxValueChildIndex = rightChildNodeIndex;
        }

        // 如果 当前node 是叶子节点，即当前node没有孩子节点，则 返回自己的index
        return maxValueChildIndex;

    }

    private int getMinValueChildIndex(int[] regularHeap,int nodeIndex, int endIndex) {

        // 左孩子的index
        int leftChildNodeIndex = this.getLeftChildNodeIndex(nodeIndex);
        // 右孩子的index
        int rightChildNodeIndex = leftChildNodeIndex + 1;

        int minValueChildIndex = nodeIndex;

        // 如果有左孩子，即如果 当前node不是叶子节点，返回左节点的index
        if (leftChildNodeIndex < endIndex && regularHeap[leftChildNodeIndex-1] < regularHeap[nodeIndex-1])
            minValueChildIndex = leftChildNodeIndex;

        // 如果 右孩子也存在，并且右孩子比左孩子的value还小，则返回右孩子的index
        if (rightChildNodeIndex < endIndex && regularHeap[rightChildNodeIndex-1] < regularHeap[leftChildNodeIndex-1] ){
            minValueChildIndex = rightChildNodeIndex;
        }

        // 如果 当前node 是叶子节点，即当前node没有孩子节点，则 返回自己的index
        return minValueChildIndex;

    }


    /**
     * 与大根堆对应的数组的索引，从0开始的情况，获取父索引的方法
     * @param nodeIndex
     * @return
     */

    private int getLeftChildNodeIndex(int nodeIndex) {
        if (nodeIndex < 0)
            throw new RuntimeException("错误的节点索引值");
        // 左节点， 父节点 的index * 2
        return nodeIndex << 1;
    }

    @Override
    public void sort(int[] arr, int start, int end) {

    }

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {

            System.out.print(i);
            System.out.print(" ");
            System.out.println((i << 1) + 1);
        }
    }
}
